#define USING_BUILDIN_STACK_VAR
#include "sort.h"


int compare(void* c1, void* c2){
    return *(int*)c1 - *(int*)c2;
}

//希尔排序增量函数
int increment(int start){
    static int IncrementArray[3] = {2,1,0};
    static int n = 0;
    return IncrementArray[n++];
}

void PrintIntArray(void** array, int start, int end){//从0开始，左开右闭 [start,end)
    for (int i = start; i < end; i++)
    {
        printf("%d ",*(int*)array[i]);
    }
    printf("\n");
}
//各个排序算法的基本测试
void BasicTest(){
    size_t start;//start time

    const int size = 1000000;
    int* array[size] = {NULL};
    printf("original sequence:");
    for (int i = 0; i < size; i++)
    {
        array[i] = malloc(sizeof(int));
        *array[i] = rand() % 999999;
        //printf("%d ",*array[i]);
    }
    printf("\n");

    #if 0
    //直接插入排序
    InsertSort(array,size,compare);
    PrintIntArray(array,0,size);

    //直接插入排序（带哨兵）
    InsertSortWithSentry(array,size,compare);
    PrintIntArray(array,1,size);

    //希尔排序
    ShellSort(array,size,compare,increment,0);
    PrintIntArray(array,0,size);

     //冒泡排序
    BubbleSort(array,size,compare);
    PrintIntArray(array,0,size);

     //快速排序(递归)
     start = clock();
     QuickSort(array,compare,0,size-1);
     //PrintIntArray(array,0,size);
     printf("time:%fs\n",(double)(clock()-start)/CLOCKS_PER_SEC);

    start = clock();
    //快速排序(使用栈模拟递归)
    QuickSortNonrecursively(array,compare,0,size-1);
    printf("time:%fs\n",(double)(clock()-start)/CLOCKS_PER_SEC);
    //PrintIntArray(array,0,size);
    #endif
}

//assistance test
void CommonTest(){
    int a = 3;
    int b = 4;
    stack s;
    InitStack(&s);
    s.push(&s,&a);
    s.push(&s,&b);
    printf("pop:%d\n",*(int*)s.pop(&s));
    printf("pop:%d\n",*(int*)s.pop(&s));
    s.FreeStackData(&s);
}

int main(){
    srand(time(NULL));
    
     BasicTest();

    //CommonTest();

    return 0;
}